package com.itheima.algorithm.sort;

import java.util.Arrays;
/*
插入排序
 */
public class InsertionSort {
    public static void sort(int[] a){
        for(int low=1;low<a.length;low++){
            int t=a[low];
            int i=low-1;
            //自右向左找出插入位置，如果比待插入元素大，右移空出位置
            while(i>=0 && t<a[i]){
                a[i+1]=a[i];
                i--;
            }
            //找到插入位置
            if(i!=low-1){
                a[i+1]=t;
            }
        }
    }
    public static void main(String[] args) {
        int[] a={6,5,4,3,2,1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
